import java.util.WeakHashMap;

class ListNode1{
    public int val;
    public ListNode next;
}
public class Test {
    public ListNode head;
    public boolean chkPalindrome(ListNode A){
        if (head == null){
            return true;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode cur = slow.next;
        while (cur != null){
            ListNode curNext = cur.next;
            cur.next = slow;
            slow =  cur;
            cur =  curNext;
        }
        while (head != slow){
            if (head.val != slow.val){
                return false;
            }
            if (head.next == slow){
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;



    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB){
        if (headA == null || headB == null){
            return null;
        }
        ListNode l = headA;
        ListNode s = headB;
        int lena = 0;
        int lenb = 0;
        while (l != null){
            lena++;
            l = l.next;
        }
        l = headA;
        while (s != null){
            lenb++;
            s = s.next;
        }
        s = headB;
        int len = lena - lenb;
        if (len < 0){
            l = headB;
            s = headA;
            len = lenb - lena;
        }
        while (len != 0){
            l = l.next;
            len--;
        }
        while (l != s){
            l = l.next;
            s = s.next;
        }
        return l;

    }

    public boolean hasCycle(ListNode head) {
        if (head == null){
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast != null){
            fast = fast.next.next;
            slow =  slow.next;
            if (fast == slow){
                return true;
            }
        }
        return false;

    }

    public ListNode detectCycle(ListNode head){
        if (head == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow =  slow.next;
            if (fast == slow){

                break;
            }
        }
        if (fast == null || fast.next == null){
            return null;
        }
        while (fast != slow){
            slow = slow.next;
            fast = fast.next;
        }

        return fast;
    }


}
